[This section is intended to provide a background or context to the invention that is recited in the claims. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, what is described in this section is not prior art to the description and claims in this application and is not admitted to be prior art by inclusion in this section.
Quantization is one of the main tools of lossy signal compression. The quantization process consists of finding, for a given input data, a close representative that would enable the storage or transmission of the data with less bits. A quantization function can be written as f :D->C where D is the input space and C is the set of representatives, or the codebook. For a given input from D, a representative, or codeword, is selected from C, such that a given distortion measure between the input and the representative is minimized over the entire codebook. The process of finding the codeword minimizing the distortion measure is usually called the nearest neighbor search.
If the input space, as well as the codebook, is one-dimensional, the quantization is called scalar quantization; otherwise it is called vector quantization. The representatives are also called codevectors in the case of vector quantization.
The cardinality of the codebook, CC, is smaller than that of the input space, allowing the representation of the input data on fewer bits. The index, in the codebook, of the nearest neighbor codeword, could be represented on log2 CC bits. The quantization rate, if all the codewords were represented with the same number of bits, is R=log2CC/K bits per sample, where K is the data dimension.
Generally, the nearest neighbor search involves the evaluation of the distortion measure for each codeword, which, especially for the vector quantization case, may be very expensive from the computational point of view. Various fast nearest neighbor algorithms have been proposed, that reduce the number of distortion evaluations based on one or more conditions to stop the evaluations.
Vector quantization is a tool extensively used in signal processing applications, for example in applications employing speech/audio, image or video coding.